1. Field of the Invention
This invention relates generally to the field of memory management. More particularly, the invention relates to an improved apparatus and method for allocating memory blocks.
2. Description of the Related Art
As illustrated in FIG. 1, non-volatile storage media 1000 (e.g., flash memory, hard drives, . . . etc) are typically divided into a plurality of contiguous blocks of memory. Accordingly, in order to store an application or other type of program code (e.g., “Application D”) to non-volatile memory 1000, a file system 1030 breaks the application up into blocks. In addition, to track which blocks correspond to which application, the file system 1030 generates some type of indexing data structure.
One type of indexing data structure is a file allocation table (“FAT”) which includes a pointer to each block for each application. Thus, in the example shown in FIG. 1, the FAT would include four separate pointers identifying each of the four blocks in which Application D is stored. Subsequently, when Application D is loaded into volatile memory 1010, the file system 1030 performs a lookup to the FAT to locate each of the four blocks (which, as illustrated, may or may not be stored contiguously).
Alternatively, the indexing data structure may contain a single pointer which identifies the first block in the series of blocks (e.g., block “Application D1”). Each block contains a pointer identifying the next block in the series. For example, the first block contains a pointer identifying the second block (e.g., block “Application D2”), the second block contains a pointer identifying the third block (e.g., block “Application D3”), and so on, until the final block (e.g., block “Application D4”) is reached (which contains data indicating that it is the final block in the series).
One problem which exists with current block allocation techniques is that if any portion of the indexing data structure is corrupt the entire application must be reloaded. Accordingly, if the pointer to Application D3 is lost from the FAT, there is no way to restore only this portion of the application. As such, the entire application must be reloaded and a new FAT entry identifying the application must be generated. In addition, indexing data structures may consume a significant amount of memory.
Accordingly, what is needed it an improved system and method for allocating memory blocks.